package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-17 14:06
 * @version: 1.0
 * @description: 匹配子序列的单词数
 **/
public class MatchingSubseq {
    public static void main(String[] args) {
//        String s = "abcde";
//        String[] words = {"a","bb","acd","ace"};
        String s = "dsahjpjauf";
        String[] words = {"ahjpjau","ja","ahbwzgqnuk","tnmlanowax"};
        System.out.println(numMatchingSubseq1(s,words));

    }

    /**
     * 暴力解法
     * @param s
     * @param words
     * @return
     */
    public static int numMatchingSubseq(String s, String[] words) {
        int count = 0;
        for (String word : words) {
            int j = 0;
            for (int i = 0; j < word.length() && i < s.length(); i++) {
                if(word.charAt(j) == s.charAt(i)){
                    j++;
                }
            }
            if (j == word.length()) count++;
        }
        return count;
    }


    /**
     *
     * @param s
     * @param words
     * @return
     */
    public static int numMatchingSubseq1(String s, String[] words) {
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; ++i) {
            pos[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < s.length(); ++i) {
            pos[s.charAt(i) - 'a'].add(i);
        }
        int res = words.length;
        for (String w : words) {
            if (w.length() > s.length()) {
                --res;
                continue;
            }
            int p = -1;
            for (int i = 0; i < w.length(); ++i) {
                char c = w.charAt(i);
                if (pos[c - 'a'].isEmpty() ||
                        pos[c - 'a'].get(pos[c - 'a'].size() - 1) <= p) {
                    --res;
                    break;
                }
                p = binarySearch(pos[c - 'a'], p);
            }
        }
        return res;
    }

    public static int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return list.get(left);
    }
}
